package common.test;

import common.ListNode;

/**
 * 25. K 个一组翻转链表
 */
public class _25_ReverseKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k < 1) {
            return head;
        }

        ListNode ans = new ListNode(0, head);
        ListNode pre = ans;
        ListNode tail = null;
        while (head != null) {
            for (int i = 0; i < k; i++) {
                tail = head;
                if (tail.next != null) {
                    tail = tail.next;
                } else {
                    return ans.next;
                }
            }
            ListNode newNext = tail.next;
            ListNode[] res = reverse(head, tail);
            ListNode newHead = res[0];
            ListNode newTail = res[1];
            pre.next = newHead;
            newTail.next = newNext;
            pre = newTail;
            head = newTail.next;
        }
        return ans.next;
    }

    public ListNode[] reverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode temp = p.next;
            p.next = prev;
            prev = p;
            p = temp;
        }
        return new ListNode[]{tail, head};
    }
}
